package com.entryLevel;

public class UniqueBinarySearchTrees0110_96 {

    //dp[i] 表示 有i个结点时 组成的二叉搜索树dp[i]
//    int[] dp = new int[]{};

//    ---------------------找规律
//        dp[0] = 1;
//        dp[1] = 1;
//
//        dp[2] = dp[0]*dp[1] + dp[1]*dp[0];
//        dp[3] = dp[0] * dp[2] + dp[1] * dp[1] + dp[2] * dp[0];

    //法一 递归
//    public int numTrees(int n) {
//
//        if(n==1 || n ==0) return 1;
//        int temp = 0;
//        for (int i = 0; i < n; i++) {
//            temp = numTrees(i) * numTrees(n-1 -i) + temp;
//        }
//        return temp;
//    }


    //法二 动态规划
    public int numTrees(int n) {
        if (n == 1 || n == 0) return 1;

        //dp[i] 表示 有i个结点时 组成的二叉搜索树dp[i]
        int[] dp = new int[n+1];

        //初始化
        dp[0] = 1;
        dp[1] = 1;

        for (int i = 2; i <= n; i++) {
            for (int j = 1; j <= i; j++) {
                dp[i] += dp[j-1] * dp[i - j];
            }
        }
        return dp[n];
    }

}
